package main

import "fmt"

func main() {
	tree := Constructor()
	tree.Insert("hellow")
	//fmt.Println(tree.StartsWith("hellow"))
	//fmt.Println(tree.Search("hellow"))
	tree.Insert("hello")
	fmt.Println(tree.Search("hello"))
}

type Trie struct {
	next   map[rune]*Trie
	isWord bool
}

func Constructor() Trie {
	return Trie{
		next: make(map[rune]*Trie, 26),
	}
}

func (this *Trie) Insert(word string) {
	for _, v := range word {
		if this.next[v] == nil {
			newTrie := &Trie{
				next: make(map[rune]*Trie, 26),
			}
			this.next[v] = newTrie
		}
		this = this.next[v]
	}
	this.isWord = true
}

func (this *Trie) Search(word string) bool {
	for _, v := range word {
		if this.next[v] == nil {
			return false
		}
		this = this.next[v]
	}
	return this.isWord
}

func (this *Trie) StartsWith(prefix string) bool {
	for _, v := range prefix {
		if this.next[v] == nil {
			return false
		}
		this = this.next[v]
	}
	return true
}
